/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-05-12
 * Time: 10:49
 */
class Solution7 {
    public int minimumDeleteSum(String s1, String s2) {
        int n = s1.length(),m = s2.length();

        //dp[i][j]表示s1区间[0,i]子序列和s2区间[0,j]子序列最大公共子序列的ASCII和
        int[][] dp = new int[n+1][m+1];
        //正难则反

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                if(s1.charAt(i-1) == s2.charAt(j-1)) {
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+s1.charAt(i-1));
                }
            }
        }
        //返回值
        int sum = 0;
        for(int i = 0; i < n; i++) sum += s1.charAt(i);
        for(int j = 0; j < m; j++) sum += s2.charAt(j);

        return sum - 2 * dp[n][m];
    }
}
